package com.atues.backtrack.solveSudoku;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.List;

class Solution {

    boolean rowuse[][] = new boolean[9][9], coluse[][] = new boolean[9][9];
    boolean boxuse[][][] = new boolean[3][3][9];

    List<int[]>  spaces=new ArrayList<>();
    boolean valid = false;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < 9; j++) {
                int num = board[i][j] - '0';
                if (num > 0 && num <= 9) {
                    rowuse[i][num-1] = coluse[j][num-1] = boxuse[i / 3][j / 3][num-1] = true;
                } else {
                    spaces.add(new int[]{i, j});
                }
            }
        }
        backtrack(board, 0);

    }

    //使用map记录使用情况
    void backtrack(char[][] board,int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        int[] space = spaces.get(pos);
        int i = space[0],j=space[1];
        for (int k = 0; k < 9 && !valid; k++) {
            if (!rowuse[i][k] && !coluse[j][k] && !boxuse[i/3][j/3][k]) {
                rowuse[i][k] = coluse[j][k] = boxuse[i / 3][j / 3][k] = true;
                board[i][j] = (char) (k + '0' + 1);
                backtrack(board,pos + 1);

                rowuse[i][k] = coluse[j][k] = boxuse[i / 3][j / 3][k] = false;
            }
        }

    }


}